(1) Field of the Invention
The present invention relates to an decoding method and an encoding method for decoding and encoding a variable length code using a table in which a code number corresponds to a Run symbol and a Level symbol.
(2) Description of the Related Art
Variable length coding method can be found in various standards such as JPEG, ISO/IEC 13818-2, ISO/IEC 14496-2 and ISO/IEC 14496-10. Some variable length coding methods in multimedia data coding requires the use of tables to decode a variable length code to a Run and a Level for the construction of block transform coefficients. Here, the Run is a symbol indicating the number of consecutive coefficients each having a value of zero in a block that includes quantized transform coefficients, and the Level is a symbol indicating a value of a non-zero coefficient that follows the Run.
For example, in some coding methods, two-dimensional variable length code (VLC) tables are used for decoding a single variable length code to a Run and a Level simultaneously. Such tables provide better compression than using one-dimensional VLC tables especially when the transform block size is small, for example, 4×4. FIGS. 1 to 18 show examples of two-dimensional VLC tables used in video coding standard to decode a variable length code to Run and Level information. FIG. 1 is a two-dimensional VLC table called VLC_Intra0. Furthermore, FIGS. 2 to 18 are two-dimensional VLC tables called VLC_Intra1, VLC_Intra2, VLC_Intra3, VLC_Intra4, VLC_Intra5, VLC_Intra6, VLC_Iner0, VLC_Inter1, VLC_Inter2, VLC_Inter3, VLC_Inter4, VLC_Inter5, VLC_Inter6, VLC_Chroma0, VLC_Chroma1, VLC_Chroma2, and VLC_Chroma3, respectively.
In the two-dimensional VLC tables, a pair of a Run and a Level corresponds to a code number (hereinafter, referred to also as CodeNum). In video encoding, the pair of a Run and a Level is transformed to a CodeNum based on the above VLC table, and such CodeNum is further transformed to a variable length code. Such a VLC table is called a code number table (CodeNum table).
An example of the variable length coding method using the two-dimensional CodeNum table is described as follows. In FIG. 1, the entries indicate the values of CodeNum. The rows indicate the values of Run corresponding to the CodeNum while the columns indicate the absolute values of Level corresponding to the CodeNum. For example, Run with a value of 1 and Level with a value of 2 will give a CodeNum of 18. Furthermore, CodeNum corresponding to Level with negative values can be obtained using the same table. For example, Run with a value of 1 and Level with a value of −2 will give a CodeNum of 19 (18+1=19). That is because a value of each CodeNum plus 1 in the table is a CodeNum corresponding to each Level with a negative value. In the table, even CodeNum indicate positive Level and odd CodeNum that are not found in the table indicate negative Level.
Furthermore, the CodeNum in the table can be encoded to an Exponential-Golomb (Exp-Golomb) code and vice versa.
FIG. 19 shows examples of k-type Exp-Golomb codes. Exp-Golomb codes are variable length codes where the length of the prefix bits and the length of the suffix bits follow a fixed relationship. The prefix bits are bits before the first “1” bit reading from the most significant bit to the least significant bit. The suffix bits are bits after the first “1” bit reading from the most significant bit to the least significant bit. Thus, as shown in FIG. 19, for the k-type Exp-Golomb code, the length of the suffix bits is equal to the length of the prefix bits plus k.
One conventional art for representing Run and Level information that are not present in the CodeNum tables is to use CodeNum greater than the maximum value specified in the CodeNum table to represent the Run values only. The information regarding Sign of the Level information is carried with the CodeNum table as well and a CodeNum corresponding to a positive Level plus 1 represents a CodeNum corresponding to negative Level. The second variable length code following the current variable length code represents an Exp-Golomb code to indicate the absolute value of the Level. If decoded Run information is less than the maximum value of Run indicated in the CodeNum table, a value of encoded Level value is a difference between actual Level and the maximum value of Level plus 1. Else, the encoded Level value is a difference between an absolute value of Level and one.
FIG. 20 shows a syntax of another conventional art for writing an end of block (EOB) symbol of a 4×4 block. If the 4×4 block is encoded, all the transform coefficients are not zero. As shown in FIG. 20, the transform coefficients are decoded until the decoded symbol indicates that an EOB symbol is present. Thus the last symbol of the block has to be an EOB symbol.
The conventional arts as described above have the following problems to be solved. The first problem for the first conventional art to be solved is that some redundancy is introduced into the variable length coding as not all the values of CodeNum resulting in the same bit numbers are fully assigned to the CodeNum table. For example, if the maximum possible value for Run is 15, the largest value for CodeNum will be 37+30=67 as shown in FIG. 1. And to represent this CodeNum, a 12 bit variable length code is needed for k=1 type Exp-Golomb Code, for example, “000001000101”. Thus, since the CodeNum “000001000101” corresponds to a maximum Run, the 12 bit codes from “000001000110” to “000001111111” are never used, so that some redundancy is introduced into the coding method.
The second problem for the first conventional art is that sometimes the value of Level is very large and the size of the second variable length code can be also quite large. For this case, the coding efficiency is decreased.
The problem with the second conventional art is redundancy resulted from that the last variable length code of the block always has to be the EOB symbol. If the last coefficient of the block is not zero, an end of the block can be determined by counting coefficients that are not yet decoded in the block and determining the counted number is zero, so that it is possible to determine, without using the EOB, that a currently decoding coefficient is the last coefficient in the block, so that the EOB is redundant and decreases the coding efficiency.